package io.gitee.wiqer.simple;

public class SolutionNC32_Sqrt {
    /**
     *方法一：直接遍历
     * 具体做法：
     * 从0开始遍历√x个数据；
     * @param x int整型
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        int res = 0;
        // 注意转换为 long, 否则会产生溢出
        while ((long)res * res <= x) {
            ++res;
        }
        return --res;
    }

    /**
     * 解法二：二分法
     * 具体做法：
     * 每次取x的一半 right ，判断 left 的值 与 right 除以 mid 向下取整 的比较方向，进行二分；
     * @param x
     * @return
     */
    public int sqrt_Segment (int x) {
        // write code here
        if (x < 2) {
            return x;
        }
        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            int sqrtTemp= x / mid;
            if (mid > sqrtTemp) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}
